<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,a4paper,french]{book}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage{a4}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{framed}
\usepackage{dsfont}
\usepackage[amsmath,thmmarks,thref,framed]{ntheorem}
\usepackage[dvips]{graphics}
\usepackage{epsfig}
\usepackage{calc}
\usepackage{tabls}
\usepackage{slashbox}
\usepackage{times}
\usepackage{tabularx}
\usepackage{textcomp}

\usepackage{pst-all}

\begin{document}
\includegraphics{figures/LogoIUT.eps}
\begin{center}
\begin{Huge}
Partiel de : ThÃ©orie des graphes\\
Semestre 3 (23 mars 2009)\\
\end{Huge}
\end{center}

La calculatrice, ainsi qu'un quart de feuille A4, sont autorisÃ©s. Ce sujet contient 50 affirmations justes, et 50 fausses. Vous aurez +1 Ã&nbsp; chaque valeur de vÃ©ritÃ© trouvÃ©e, -1 Ã&nbsp; chaque erreur (et 0 en absence de rÃ©ponse). Les notes seront ajustÃ©es Ã&nbsp; l'intervalle $[0;20]$ (les notes nÃ©gatives auront 0).\\

Q. 1. Les graphes hamiltoniens ont Ã©tÃ© dÃ©finis au dix-neuviÃ¨me siÃ¨cle.\\

Q. 2. Une chaÃ®ne dans lequel tous les sommets sont diffÃ©rents sâ€™appelle une chaÃ®ne simple.\\

Q. 3. Un graphe hamiltonien peut possÃ©der un sommet de degrÃ© 2.\\

Q. 4. Soit $J$ la matrice d'adjacence d'un graphe non orientÃ©. $J_{s,\varepsilon}$ vaut :
\begin{itemize}
\item 1 quand $s$ est une extrÃ©mitÃ© de l'arÃªte $\varepsilon$ si celle-ci n'est pas une boucle,
\item 2 quand $s$ est une extrÃ©mitÃ© de la boucle $\varepsilon$,
\item 0 si $s$ n'est pas une extrÃ©mitÃ© de $\varepsilon$.
\end{itemize}

Q. 5. Un graphe hamiltonien peut possÃ©der un sommet de degrÃ© 3.L'assertion proposÃ©e est vraie ou fausse\\

Q. 6. La matrice d'adjacence d'un graphe non orientÃ© est symÃ©trique.\\

Q. 7. Un graphe est dit planaire si on arrive Ã&nbsp; le dessiner sans qu'aucune arÃªte n'en coupe une autre.\\

Q. 8. L'inventeur des nombres complexes est aussi l'inventeur des graphes euleriens.\\

Q. 9. Un circuit eulÃ©rien est un circuit qui passe par tous les sommets du graphe.\\

Q. 10. Soit G un graphe connexe non eulÃ©rien. Il est toujours possible de rendre G eulÃ©rien en lui rajoutant un sommet et quelques arÃªtes.\\

Q. 11. S'il existe un sommet qui est connectÃ© Ã&nbsp; tous les autres, alors le graphe considÃ©rÃ© est connexe.\\

Q. 12. Le graphe suivant est biparti.

\begin{center}
\includegraphics[scale=0.7]{figures/completK5.eps}
\end{center}

Q. 13. Dans une matrice d'incidence, la somme des coefficients de la ligne $i$ est le degrÃ© du sommet $i$.\\

Q. 14.
Le graphe $G$ :

\begin{center}
\includegraphics[scale=0.75]{figures/graphe1bx.eps}
\end{center}

a pour matrice d'incidence :

$$M = \left(
\begin{array}{ccccc}
0 ~~ 0 ~~ 1 ~~ 1 ~~ 1\\
0 ~~ 0 ~~ 1 ~~ 0 ~~ 0\\
1 ~~ 1 ~~ 0 ~~ 1 ~~ 1\\
1 ~~ 0 ~~ 1 ~~ 0 ~~ 1\\
1 ~~ 0 ~~ 1 ~~ 1 ~~ 0\\
\end{array}
\right)
$$\\

Q. 15. Le graphe suivant est biparti.

\begin{center}
\includegraphics[scale=0.7]{figures/arbre1.eps}
\end{center}

Q. 16. $K_6$ est complet.\\

Q. 17. Le graphe suivant est complet

\begin{center}
\includegraphics[scale=0.7]{figures/biparti.eps}
\end{center}

Q. 18. Un graphe est dit planaire si toutes ses reprÃ©sentations sont telles qu'aucune arÃªte n'en coupe une autre.\\

Q. 19. Une chaÃ®ne dont le dÃ©part et l'arrivÃ©e coÃ¯ncident s'appelle un chemin.\\

Q. 20. Le graphe suivant est eulÃ©rien

\begin{center}
\includegraphics[scale=0.7]{figures/grapheNonConnexe.eps}
\end{center}

Q. 21. Le graphe ci-dessous est eulÃ©rien.

\begin{center}
\includegraphics[scale=0.7]{figures/arbre1.eps}
\end{center}

Q. 22. La question Ã&nbsp; l'origine du problÃ¨me des graphes hamiltoniens est : comment passer une, et une seule fois, par chacun des sommets du dodÃ©caÃ¨dre, de telle maniÃ¨re que le dernier sommet visitÃ© est aussi le premier.\\

Q. 23. Un arbre est un graphe non orientÃ©.\\

Q. 24. Le graphe suivant est connexe.

\begin{center}
\includegraphics[scale=0.7]{figures/completK5.eps}
\end{center}

Q. 25. Un arbre est un graphe non orientÃ© sans cycle.\\

Q. 26. Les expressions chaÃ®ne simple et chemin sont synonymes.\\

Q. 27. Le graphe suivant est eulerien.

\begin{center}
\includegraphics[scale=0.7]{figures/completK5.eps}
\end{center}

Q. 28. La matrice d'incidence est carrÃ©e.\\

Q. 29. $K_{m,n}$ possÃ¨de $m+n$ arÃªtes.\\

Q. 30. Le degrÃ© du graphe suivant est 5.

\begin{center}
\includegraphics[scale=0.7]{figures/completK5.eps}
\end{center}

Q. 31. Le graphe suivant est planaire.

\begin{center}
\includegraphics[scale=0.7]{figures/completK5.eps}
\end{center}

Q. 32. Le degrÃ© du graphe suivant est 20.

\begin{center}
\includegraphics[scale=0.7]{figures/completK5.eps}
\end{center}

Q. 33. Un graphe est connexe s'il est possible, Ã&nbsp; partir de n'importe quel sommet, d'atteindre n'importe quel autre sommet du graphe.\\

Q. 34.
Soit G un graphe. Le graphe G' est un graphe partiel de G, si on obtient G' en enlevant un ou plusieurs sommets au graphe G (avec les arÃªtes associÃ©es).\\

Q. 35. $K_n$ possÃ¨de $n^2$ arÃªtes.\\

Q. 36. Le graphe suivant est biparti

\begin{center}
\includegraphics[scale=0.7]{figures/grapheNonConnexe.eps}
\end{center}

Q. 37.
On considÃ¨re des dominos dont les faces sont numÃ©rotÃ©es 1, 2, 3, 4 ou 5. Il est toujours possible d'arranger ces dominos de maniÃ¨re Ã&nbsp; former une boucle fermÃ©e.\\

Q. 38. Le nombre maximal d'arÃªtes dans un graphe non orientÃ© d'ordre $n$ qui ne possÃ¨de ni arÃªtes parallÃ¨les, ni boucles, est de $n^{2}$.\\

Q. 39. Tous les $K_n$ sont hamiltoniens.\\

Q. 40. Il existe des graphes 3-rÃ©guliers simples Ã&nbsp; 6 sommets.\\

Q. 41.
ReprÃ©senter un graphe sous la forme d'une liste d'adjacence consiste Ã&nbsp; donner, pour chacun de ses sommets, la liste des sommets auxquels il est adjacent.\\

Q. 42.
On appelle chaÃ®ne eulÃ©rienne une chaÃ®ne contenant une et une seule fois toutes les arÃªtes du graphe.\\

Q. 43.
La question Ã&nbsp; l'origine du problÃ¨me des graphes hamiltoniens est : comment passer une, et une seule fois, par chacun des sommets du dodÃ©caÃ¨dre.\\

Q. 44. Si le graphe considÃ©rÃ© n'a pas de boucle, alors la matrice d'adjacence associÃ©e a une diagonale nulle.\\

Q. 45. Il peut y avoir plusieurs circuits hamiltoniens dans un graphe hamiltonien.\\

Q. 46. Le graphe suivant est simple

\begin{center}
\includegraphics[scale=0.7]{figures/grapheNonSimple.eps}
\end{center}

Q. 47. Pour tout $n$, $K_n$ est complet.\\

Q. 48. Un graphe hamiltonien peut possÃ©der un sommet de degrÃ© 3.\\

Q. 49. Un circuit eulÃ©rien est un circuit qui passe par toutes les arÃªtes du graphe.L'assertion proposÃ©e est vraie ou fausse\\

Q. 50. $K_n$ possÃ¨de $\dfrac{n(n-1)}{2}$ sommets.\\

Q. 51. Le graphe suivant est hamiltonien.

\begin{center}
\includegraphics[scale=0.7]{figures/completK5.eps}
\end{center}

Q. 52.
\begin{center}
\includegraphics[scale=0.7]{figures/graphe9.eps}
\end{center}

est un sous-graphe de

\begin{center}
\includegraphics[scale=0.7]{figures/graphe7.eps}
\end{center}

Q. 53. Hamilton est Ã&nbsp; l'origine du problÃ¨me des graphes eulÃ©riens.\\

Q. 54. Un graphe hamiltonien ne possÃ¨de pas de sommets de degrÃ© 1.L'assertion proposÃ©e est vraie ou fausse\\

Q. 55. Le corollaire de Dirac se dÃ©duit du thÃ©orÃ¨me de Ore.L'assertion proposÃ©e est vraie ou fausse\\

Q. 56.
PossÃ©der un circuit eulÃ©rien est Ã©quivalent Ã&nbsp; n'avoir aucun sommet de degrÃ© impair.\\

Q. 57. Un circuit hamiltonien est un circuit qui passe par toutes les arÃªtes du graphe.\\

Q. 58. Il existe des graphes qui peuvent Ãªtre hamiltoniens sans Ãªtre eulÃ©riens.\\

Q. 59. $K_5$ est hamiltonien.\\

Q. 60.
\begin{center}
\includegraphics[scale=0.7]{figures/graphe9.eps}
\end{center}

est un stable de

\begin{center}
\includegraphics[scale=0.7]{figures/graphe7.eps}
\end{center}

Q. 61. Dans le cas des graphes orientÃ©s, on parle de chemins, et dans le cas non orientÃ©, de chaÃ®nes.\\

Q. 62. Dans le graphe suivant, le sommet 1 a pour degrÃ© 4.

\begin{center}
\includegraphics[scale=0.7]{figures/completK5.eps}
\end{center}

Q. 63. Le graphe suivant est connexe.

\begin{center}
\includegraphics[scale=0.7]{figures/biparti.eps}
\end{center}

Q. 64.
Dans un circuit eulÃ©rien, le point de dÃ©part et d'arrivÃ©e coÃ¯ncident.\\

Q. 65. Le thÃ©orÃ¨me de Ore s'Ã©nonce ainsi : Soit G = (V, E) un graphe simple d'ordre $n\geqslant 3$. Si pour toute paire \{x,y\} de sommets non adjacents, on a $d(x) + d(y) \geqslant n$, alors G est hamiltonien.\\

Q. 66.
Etre un graphe eulÃ©rien est Ã©quivalent Ã&nbsp; Ãªtre connexe, sans sommet de degrÃ© impair.\\

Q. 67. Un circuit hamiltonien est un circuit qui passe par tous les sommets du graphe.L'assertion proposÃ©e est vraie ou fausse\\

Q. 68.
\begin{center}
\includegraphics[scale=0.7]{figures/graphe8.eps}
\end{center}

est un sous-graphe partiel de

\begin{center}
\includegraphics[scale=0.7]{figures/graphe7.eps}
\end{center}

Q. 69.
PossÃ©der un circuit eulÃ©rien est Ã©quivalent Ã&nbsp; avoir 0 ou 2 sommets de degrÃ© impair.\\

Q. 70. Un graphe est dit complet s'il est en un seul tenant.\\

Q. 71.
Etre un graphe eulÃ©rien est Ã©quivalent Ã&nbsp; n'avoir aucun sommet de degrÃ© impair.\\

Q. 72.
Le graphe suivant est-il eulÃ©rien ?

\begin{center}
\includegraphics[scale=0.7]{figures/eulerKonig}
\end{center}

Q. 73. Il existe des graphes 3-rÃ©guliers simples Ã&nbsp; 8 sommets.\\

Q. 74. Le graphe suivant s'appelle $K_5$.

\begin{center}
\includegraphics[scale=0.7]{figures/completK5.eps}
\end{center}

Q. 75. Un graphe hamiltonien ne possÃ¨de pas de sommets de degrÃ© 1.\\

Q. 76. $K_{m,n}$ dÃ©signe tout graphe ayant deux composantes connexes, la premiÃ¨re avec $m$ sommets, et la seconde avec $n$ sommets.\\

Q. 77. Un graphe connexe est complet.\\

Q. 78. Le corollaire de Dirac sert Ã&nbsp; dÃ©terminer si un graphe est eulÃ©rien.L'assertion proposÃ©e est vraie ou fausse\\

Q. 79. Le degrÃ© d'un graphe est son nombre d'arÃªtes.\\

Q. 80. Un graphe dont tous les sommets ont le mÃªme degrÃ© est dit rÃ©gulier.\\

Q. 81.
Etre un graphe eulÃ©rien est Ã©quivalent Ã&nbsp; Ãªtre connexe, avec 0 ou 2 sommets de degrÃ© impair.\\

Q. 82. Le nombre maximal d'arÃªtes dans un graphe non orientÃ© d'ordre $n$ qui ne possÃ¨de pas d'arÃªtes parallÃ¨les, est de $n^{2}$.\\

Q. 83.
PossÃ©der une chaÃ®ne eulÃ©rienne est Ã©quivalent Ã&nbsp; Ãªtre connexe, sans sommet de degrÃ© impair.\\

Q. 84.
Le graphe $(S',A')$ est un sous-graphe du graphe $(S,A)$ si
\begin{enumerate}
\item $S' \subset S$,
\item $A' \subset A$,
\item $A'=\{(x,y)\mid (x,y) \in A \land x \in S' \land y \in S'\}$
\end{enumerate}

Q. 85.
On considÃ¨re des dominos dont les faces sont numÃ©rotÃ©es de 1 Ã&nbsp; 7. Il est toujours possible d'arranger ces dominos de maniÃ¨re Ã&nbsp; former une boucle fermÃ©e.\\

Q. 86.
Un graphe eulÃ©rien est un graphe possÃ©dant un circuit eulÃ©rien.\\

Q. 87. Le corollaire de Dirac s'Ã©nonce ainsi : Soit G = (V, E) un graphe simple d'ordre $n\geqslant 3$. Si pour toute paire \{x,y\} de sommets non adjacents, on a $d(x) + d(y) \geqslant n$, alors G est hamiltonien.L'assertion proposÃ©e est vraie ou fausse\\

Q. 88. Un graphe hamiltonien ne possÃ¨de pas de sommets de degrÃ© 3.\\

Q. 89. Un graphe est dit simple, sâ€™il ne contient pas de boucles et sâ€™il nâ€™y a pas plus dâ€™une arÃªte reliant deux mÃªmes sommets.\\

Q. 90. $K_2$ est hamiltonien.\\

Q. 91. Le graphe suivant est rÃ©gulier.

\begin{center}
\includegraphics[scale=0.7]{figures/arbre1.eps}
\end{center}

Q. 92. Un graphe hamiltonien ne possÃ¨de pas de sommets de degrÃ© 2.L'assertion proposÃ©e est vraie ou fausse\\

Q. 93.
\begin{center}
\includegraphics[scale=0.7]{figures/graphe8.eps}
\end{center}

est un graphe partiel de

\begin{center}
\includegraphics[scale=0.7]{figures/graphe7.eps}
\end{center}

Q. 94. Le corollaire de Dirac se dÃ©duit du thÃ©orÃ¨me de Ore.\\

Q. 95. Un graphe simple a un nombre impair de sommets de degrÃ© pair.\\

Q. 96. Le nombre maximal d'arÃªtes dans un graphe non orientÃ© d'ordre $n$ qui ne possÃ¨de pas d'arÃªtes parallÃ¨les, est de $\dfrac{n(n+1)}{2}$.\\

Q. 97. $K_n$ possÃ¨de $n$ sommets.\\

Q. 98. Le lemme des poignÃ©es de mains dit que la somme des degrÃ©s des sommets est Ã©gale Ã&nbsp; deux fois le nombre d'arÃªtes.\\

Q. 99. $K_4$ est hamiltonien.\\

Q. 100.
Le graphe $G$ suivant :
\begin{center}
\includegraphics[scale=0.7]{figures/graphe1b.eps}
\end{center}

\noindent PossÃ¨de pour liste d'adjacence :

1 : 3, 4, 5

2 : 3

3 : 1, 2, 5

4 : 1, 3, 5

5 : 1, 3, 4\\

\end{document}
</pre></body></html>